package us.kg.kotoriforest.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/rotting-oranges/">994. 腐烂的橘子</a>
 *
 * @author Kotori rotroutine@163.com
 * @since 2025/1/29
 */
public class OrangesRotting {
    private final int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
    private int m, n;
    private int fresh; // 新鲜橘子的个数
    private final List<int[]> rot = new ArrayList<>(); // 腐烂橘子的坐标

    public int orangesRotting(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (1 == grid[i][j]) ++fresh;
                else if (2 == grid[i][j]) rot.add(new int[]{i, j});
            }
        }

        // 只有空格子
        if (0 == fresh && rot.isEmpty()) return 0;

        int ans = 0;
        for (int last = 0; last != rot.size();) {
            last = rot.size();
            for (int i = 0; i < last; ++i) {
                int[] pos = rot.get(i);
                bfs(grid, pos[0], pos[1]);
            }

            ++ans;
        }

        return 0 == fresh ? ans - 1 : -1;
    }

    // 输入一个腐烂橘子的坐标 将其上下左右全感染
    private void bfs(int[][] grid, int i, int j) {
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k], y = j + dy[k];
            if (x < 0 || x == m || y < 0 || y == n) continue; // 越界不处理
            if (1 == grid[x][y]) {
                grid[x][y] = 2;
                --fresh;
                rot.add(new int[]{x, y});
            }
        }
    }

    public static void main(String[] args) {
        int[][] grid = {
                {2, 1, 1},
                {1, 1, 0},
                {0, 1, 1}
        };

        System.out.println(new OrangesRotting().orangesRotting(grid));

        int numCourses = 2;
        List<Integer>[] dependencies = new ArrayList[numCourses];
        Arrays.setAll(dependencies, ArrayList<Integer>::new);
    }
}
